package 划分为k个相等的子集;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * @author: AirMan
 * @date: 2025/5/7 11:06
 * @description: 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等
 * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * 输出： True
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 */
public class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 采用回溯方法将进行解决
        // ① 回溯函数的参数和返回值：nums，index, int[] bucket
        // ② 回溯的终止条件：start == nums.length
        // ③ 回溯搜索的遍历过程：目标是找到k个树节点，且改树节点的值等于 sum/k，且这些树节点刚好组成nums
        // 想象树的每一层都是nums[i]做选择，选择进入哪一个桶中！

        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;
        int target = sum / k;
        // 排序优化 ==> 降序排序，更早的发现是否能够划分数组（因为bucket先拿到的是大数字）
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
        System.out.println(Arrays.toString(nums));
        return backTracking(nums, 0, new int[k], target);
    }

    public boolean backTracking(int[] nums, int index, int[] bucket, int target) {
        /*if (index == nums.length) {
            for (int bucketSum : bucket) {
                if (bucketSum != target) return false;
            }
            return true;
        }*/
        // 结束条件优化！ 第一次数显 index == nums.length 的时候，bucket中所有的元素值一定是 target
        if (index == nums.length) {
            return true;
        }

        // 从数字的视角看
        for (int i = 0; i < bucket.length; i++) {
            // 剪枝
            // 如果当前桶和上一个桶内的元素和相等，则跳过(元素可重不可复选)
            // 原因：如果元素和相等，那么 nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的
            if (i > 0 && bucket[i] == bucket[i - 1]) continue;
            if (bucket[i] + nums[index] > target) continue;

            bucket[i] += nums[index];
            if (backTracking(nums, index + 1, bucket, target)) return true;
            bucket[i] -= nums[index];
        }

        return false;
    }
}
